1. Field of the Invention
This invention relates generally to cryptography and more particularly to a system and method for regenerating secret keys involved in Diffie-Hellman exchanges. Upon regeneration of secret keys, messages in secret communications are decrypted and observed.
2. Description of the Background Art
Cryptography involves the enciphering and deciphering of messages in a secret code, and has utility in the field of secure communications where issues of privacy and authentication of messages in public communications are important concerns. A privacy system prevents the extraction by unauthorized parties ("eavesdroppers") of information from messages transmitted over a communication channel, thus assuring that only the intended recipient is able to read the message. An authentication system prevents unauthorized intermeddling with the message from unintended parties ("intermeddlers"), assuring the party at the receiving side that the message is that intended by its sender. The authentication system also assures the recipient that the sender is the party the message was actually sent from. Depending upon safeguards, any communication channel may be threatened with eavesdropping and intermeddling, which thereby threatens the integrity of the messages or the identities of the transmitters.
FIG. 1 illustrates the flow of information in a conventional cryptographic communication. There are three parties: a transmitter 102, a receiver 104, and an eavesdropper or intermeddler 106. The transmitter 102 generates a message 108 to be communicated over a communication channel to the receiver 104. In order to prevent the eavesdroppers and intermeddlers 106 from reading the messages, transmitter 102 encrypts the messages 108 using a cryptography key 110 producing encrypted messages 112, which are sent to the receiver 104 over communications media 114. The legitimate receiver 104 must know how to decrypt the encrypted messages 112 using decrypting key 116 to have access to the original message 108. The roles of transmitter 102 and receiver 104 are reversible, that is, a receiver 104 becomes a transmitter 102, which transmits encrypted messages 112 to the former transmitter 102, which in turn becomes receiver 104.
Encrypted messages in communication systems solve message security problems when message encryption techniques are properly used in the hands of legitimate personnel. However, in the hands of criminals or terrorists, encrypted communications are an aid to illegal activities because the messages in the communications are secret to the public. The United States Government, in light of the needs to prevent illegitimate activities, has required that it have access to encrypted communications so that it can observe the original, unencrypted messages 108. The government therefore has proposed various plans which require the parties involved in encrypted communications to hold, or "escrow," the encryption keys 110 used to encrypt messages 108 for some period of time. These encryption keys 110 must be readily surrendered to the government upon request. Having acquired the encryption keys 110, the government then has access to the original messages 108 through decryption of the messages 112 which are exchanged between suspect parties.
The requirement to hold encryption keys for a long period of time has great impact on embedded communications devices, especially routers, as most routers do not have any hard disk or other memory devices to store encryption keys. Additionally, it is desirable to implement a cryptographic scheme utilizing ephemeral keys which are derived from a Diffie-Hellman exchange, with one key per communication session. These ephemeral keys are then destroyed after each session. Federal law mandates access to keys for a period of up to seven years, requiring storage of hundreds of thousands of keys since hundreds of thousands of communication sessions may occur in a period of seven years with each session generating a unique key. Moreover, it is desirable to embrace a standard where any key escrow scheme does not preclude interoperability with existing standards. For example, if one party implements a key escrow scheme and others do not implement that key escrow scheme, it is desirable that the party with the escrow scheme is not precluded from inter-operating with the others. It is further desirable that a key escrow scheme can be seamlessly added to any standard-complaint key management protocol which utilizes a Diffie-Hellman exchange in order to additionally generate ephemeral secret keys such that the additional implementation which performs escrow remains fully standard-compliant. The escrow requirement thus raises the concern that the escrow of keys must be done securely, i.e., with full proof of security and authentication.
Attempts at escrowing ephemeral keys have been discussed by Silvio Micali, "Guaranteed Partial Key-Escrow," MIT/LCS/TM-537, Laboratory for Computer Science, Massachusetts Institutes of Technology, Cambridge, Cambridge, Mass. (1995); and by Mihir Bellare and Shafi Goldwasser, "Verifiable Partial Key Escrow," University of California, San Diego, CSE Department Technical Report. Both of these papers describe key escrow schemes that take advantage of a Diffie-Hellman exchange and allow for recovery of communications using a partially escrowed key. Each key used for bulk encryption by a router, for example, is partially escrowed. However, each of these schemes concerns only the partial escrow of a single ephemeral key, and does not deal with the problem of ephemeral session keys, where hundreds or thousands of keys are generated during a period of time of up to seven years.
A key escrow scheme applicable to network communications devices is discussed in "Escrowed Encryption Standard (ESS)," National Institute for Standards and Technology, Federal Information Processing Standards Publication (FIPS PUB) 185, 1994. However, this approach involves a hardware solution, and requires both parties in a communication to be active participants in the escrow operation.
Another key escrow scheme, also applicable to network communications devices, is disclosed by Jim Omura, "Alternatives to RSA Using Diffie-Hellman with DSS," White Paper, Cylink, September 1995. In this scheme, the escrowing party sends the key to an escrow agent, and the agent in return provides the escrowee a public number to use in the next Diffie-exchange. However, this scheme involves the escrow of a single key and requires interaction with the escrow agent for each key.
In light of the above shortcomings of prior art techniques in encryption key escrowing, there is a need for an implementation that allows a complete recovery of all encryption keys involved in Diffie-Hellman exchanges and yet still prevents eavesdroppers and intermeddlers from capturing the secrets of private communications. In accordance with the present invention, there are no special headers or messages required between parties for secure communications. Neither is there a special hardware requirement for any party involved in the communications.
Therefore, it is an object of this invention to provide a key-escrowing scheme that requires only a single interaction with the escrow agent during a time period of variable length and eliminates the needs to escrow each and every key, and where there is no necessity to store all of the session keys while preserving the ephemeral nature of these keys.
It is a further object of this invention to remove the requirement that a participating networking communication device maintain session keys after the life of the session has passed, and thereby to retain the ephemeral nature of the keys.
It is still a further object of the invention to allow a party to take part in an escrow and to continue inter-operating with existing standards and methods of secured communications.
It is a further object of the invention to allow a solution that is applicable to all devices on a network, including hosts, servers and routers.
It is still a further object of the invention to allow third party law enforcement officers to recover communication information and to monitor messages exchanged between the parties taking part in the Diffie-Hellman communications.
It is still a further object of the invention to allow recovery of the communication even if only one party was involved in the escrowing scheme.
It is still a further object of the invention to maintain the security strength of the Diffie-Hellman exchange.
It is still a further object of the invention to escrow the key to the escrowing center with confidentiality and proof of ownership, thereby assuring both privacy and authenticity of the escrowed information.